{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "b9d9f59c",
   "metadata": {},
   "source": [
    "## 移除链表中的元素\n",
    "给定一个链表的头节点 `head` 和一个整数 `val`，请你删除链表中所有满足 `Node.val == val` 的节点，并返回 新的头节点 。首先我们需要定义链表节点的结构体 `ListNode`，然后实现一个函数 `removeElements` 来删除链表中所有值为 `val` 的节点。最后，我们还需要一个辅助函数 `print_list` 来打印链表的值，以便于验证结果。\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5b4b05dd",
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import Optional\n",
    "class ListNode:\n",
    "    def __init__(self,val=0,next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\n",
    "class solution:\n",
    "    def removeElement(self,head:Optional[ListNode],target) -> Optional[ListNode]:\n",
    "        dummy_head = ListNode(next=head)\n",
    "        current = dummy_head\n",
    "        while current.next:\n",
    "            if current.next.val == target:\n",
    "                current.next = current.next.next\n",
    "            else:\n",
    "                current = current.next\n",
    "        return dummy_head \n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3b182ea7",
   "metadata": {},
   "source": [
    "## 设计链表\n",
    "[力扣题目链接](https://leetcode.cn/problems/design-linked-list/)\n",
    "* get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。\n",
    "* addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。\n",
    "* addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。\n",
    "* addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val  的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。\n",
    "* deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "15ae5304",
   "metadata": {},
   "outputs": [],
   "source": [
    "class ListNode:\n",
    "    def __init__(self,val=0,next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\n",
    "class MyLinkedList:\n",
    "    def __init__(self):\n",
    "        self.dummy_head = ListNode()\n",
    "        self.size = 0\n",
    "\n",
    "    def get(self,index:int) -> int:\n",
    "        if index < 0 or index >= self.size:\n",
    "            return -1\n",
    "        \n",
    "        current = self.dummy_head.next\n",
    "        for i in range(index):\n",
    "            current = current.next\n",
    "        \n",
    "        return current.val\n",
    "\n",
    "    def addAtHead(self,val:int) -> None:\n",
    "        self.dummy_head.next = ListNode(val,self.dummy_head.next)\n",
    "        self.size += 1\n",
    "\n",
    "    def addAtTail(self,val: int) -> None:\n",
    "        current = self.dummy_head\n",
    "        while current.next:\n",
    "            current = current.next\n",
    "        current.next = ListNode(val)\n",
    "        self.size += 1\n",
    "    \n",
    "    def addAtIndex(self, index: int,val: int)  -> None:\n",
    "        if index < 0 or index > self.size:\n",
    "            return\n",
    "        \n",
    "        current = self.dummy_head\n",
    "        for i in range(index):\n",
    "            current = current.next\n",
    "        current.next = ListNode(val,current.next)\n",
    "        self.size += 1\n",
    "\n",
    "    def deleteAtIndex(self, index: int) -> None:\n",
    "        if index < 0 or index >= self.size:\n",
    "            return \n",
    "        \n",
    "        current = self.dummy_head\n",
    "        for i in range(index):\n",
    "            current = current.next\n",
    "        current.next = current.next.next\n",
    "        self.size -= 1\n",
    "\n",
    "    \n",
    "\n",
    "    \n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "env_py38",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3.8.18"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
